import java.util.Scanner;

/*class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}*/
public class Main {

    /*
    * 判断一颗二叉树是否是平衡二叉树
      给定一个二叉树，判断它是否是高度平衡的二叉树。
      本题中，一棵高度平衡二叉树定义为：
      一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。
    * */

    public boolean isBalanced(TreeNode root){
        if(root==null){
            return false;
        }
        if(Math.abs(getHeight(root.left)-getHeight(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);

    }
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归地计算节点的高度
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        // 返回节点的高度（左右子树中较大的高度加上1）
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /*给你一个二叉树的根节点 root ， 检查它是否轴对称。*/

        public boolean isSymmetric(TreeNode root){
            if(root==null){
                return true;
            }
            return isMirror(root.left,root.right);
        }
        public boolean isMirror(TreeNode node1,TreeNode node2){
            if(node1==null&&node2==null) return true;
            if ((node1==null&&node2!=null)||(node1!=null&&node2==null)||node1.val!=node2.val) return false;
            return isMirror(node1.left,node2.right)&&isMirror(node1.right,node2.left);
        }
/*
二叉树的构建及遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串：
 ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
* */



    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode(char val) {
            this.val = val;
        }
    }


        private static int index = 0;

        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNextLine()) {  // 循环读取输入的每一行
                String preorder = in.nextLine();  // 读取先序遍历字符串
                TreeNode root = buildTree(preorder);  // 构建二叉树
                String inorder = inorderTraversal(root);  // 中序遍历二叉树
                System.out.println(inorder);  // 打印中序遍历结果
            }
        }

        private static TreeNode buildTree(String preorder) {
            index = 0;  // 重置索引为0
            return buildTreeHelper(preorder);  // 调用辅助方法构建二叉树
        }

        private  static  TreeNode buildTreeHelper(String preorder) {
            if (index >= preorder.length()) {  // 如果索引超出字符串长度，表示已遍历完，返回null
                return null;
            }

            char ch = preorder.charAt(index++);  // 获取当前字符，并将索引增加1
            if (ch == '#') {  // 如果当前字符是'#'，表示是空节点，返回null
                return null;
            }

            TreeNode node = new TreeNode(ch);  // 创建新的二叉树节点
            node.left = buildTreeHelper(preorder);  // 递归构建左子树
            node.right = buildTreeHelper(preorder);  // 递归构建右子树

            return node;  // 返回构建好的节点
        }

        private static String inorderTraversal(TreeNode root) {
            StringBuilder sb = new StringBuilder();  // 创建StringBuilder对象，用于保存中序遍历结果
            inorderTraversalHelper(root, sb);  // 调用辅助方法进行中序遍历
            return sb.toString();  // 返回中序遍历结果的字符串形式
        }

        private static void inorderTraversalHelper(TreeNode node, StringBuilder sb) {
            if (node == null) {  // 如果节点为空，表示到达叶子节点，直接返回
                return;
            }

            inorderTraversalHelper(node.left, sb);  // 递归遍历左子树
            sb.append(node.val).append(" ");  // 将当前节点值添加到结果中
            inorderTraversalHelper(node.right, sb);  // 递归遍历右子树
        }
    }


